/*
 * $Id$
 *
 * Hashtable implementation for Symbian environments
 * Copyright (C) 2006 Matti Dahlbom
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation; either
 * version 2.1 of the License, or (at your option) any later version.
 *
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public
 * License along with this library; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 *
 * Contact: Matti Dahlbom <matti at 777-team.org>
 */

#ifndef __HASHTABLE_H
#define __HASHTABLE_H

const TInt KDefaultTableSize = 100;
const TReal KDefaultRehashRatio = 0.75;

/**
 * Hashtable entry.<p />
 *
 * @author Matti Dahlbom
 * @version $Name:  $, $Revision: 1.2 $
 */
template<class T, TBool OwnsObj = ETrue> class CHashTableEntry: public CBase
	{
public:
	// Constructors and destructor
	static CHashTableEntry<T, OwnsObj>* NewL(const TDesC8& aKey, T* aObj);
	~CHashTableEntry();

public:
	// New methods
	const TDesC8& Key() const
		{
		return *iKey;
		}

	T* Obj() const
		{
		return iObj;
		}

	CHashTableEntry<T, OwnsObj>* Next() const
		{
		return iNext;
		}

	void SetNext(CHashTableEntry<T, OwnsObj>* aNext)
		{
		iNext = aNext;
		}

private:
	// Constructors
	void ConstructL(const TDesC8& aKey);
	CHashTableEntry<T, OwnsObj> (T* aObj);

private:
	// Data
	HBufC8* iKey;
	T* iObj;
	CHashTableEntry<T, OwnsObj>* iNext;
	};

template<class T, TBool OwnsObj> class CEntryIterator;

/**
 * Templated hash table implementantion, using strings (descriptors) as keys.<p />
 *
 * @author Matti Dahlbom
 * @version $Name:  $, $Revision: 1.2 $
 */
template<class T, TBool OwnsObj = ETrue> class CHashTable: public CBase
	{
public:
	// Constructors and destructor
	static CHashTable* NewL(TInt aInitialTableSize = KDefaultTableSize, TReal aRehashRatio = KDefaultRehashRatio);
	static CHashTable* NewLC(TInt aInitialTableSize = KDefaultTableSize, TReal aRehashRatio = KDefaultRehashRatio);
	virtual ~CHashTable();

public:
	// New methods
	/**
	 * Puts a new entry in the hash table. If en entry with matching key
	 * is found already, it will be replaced. This class will assume the
	 * ownership of the object pointed to by <code>aObj</code>.<p />
	 */
	void PutL(const TDesC8& aKey, T* aObj);

	/**
	 * Returns <code>NULL</code> if there is no matching entry.<p />
	 */
	T* GetL(const TDesC8& aKey) const;

	/**
	 * Removes the entry with given key.<p />
	 *
	 * @return ETrue if the table held entry for the given key
	 */
	TBool Remove(const TDesC8& aKey);

	/**
	 * Resets the table, deallocating all entries. The table itself stays untouched, 
	 * keeping its current maximum size.
	 */
	void ResetTable();

	void RehashL();
	CEntryIterator<T, OwnsObj>* EntriesLC() const;
	TReal LoadFactor();
	TInt NumEntries() const;

private:
	// New methods
	void InsertIntoTableL(const TDesC8& aKey, T* aObj, CHashTableEntry<T, OwnsObj>** aTable, TUint aIndex, TInt& aNumEntries);
	void InsertIntoTable(CHashTableEntry<T, OwnsObj>* aEntry, CHashTableEntry<T, OwnsObj>** aTable, TUint aIndex, TInt& aNumEntries);
	TUint Hash(const TDesC8& aKey, TInt aTableSize) const;
	void AllocateTableL(CHashTableEntry<T, OwnsObj>**& aTable, TInt aTableSize);
	void DeallocateTable();

protected:
	// Constructors
	virtual void ConstructL();
	CHashTable(TInt aInitialTableSize = KDefaultTableSize, TReal aRehashRatio = KDefaultRehashRatio);

private:
	// Data
	CHashTableEntry<T, OwnsObj>** iTable;
	TInt iTableSize;
	TReal iRehashRatio;
	TInt iNumEntries;
	};

/**
 * Iterator implementation for retrieving all entries in a hashtable. The entries 
 * will not be returned in any specific order. If the hashtable is modified during 
 * the lifetime of the iterator, results may vary from missing entries to crashes.<p />
 *
 * @author Matti Dahlbom
 * @version $Name:  $, $Revision: 1.2 $
 */
template<class T, TBool OwnsObj = ETrue> class CEntryIterator: public CBase
	{
public:
	// New methods
	TBool Next(TPtrC8& aKey, T*& aValue);
	TBool Next(CHashTableEntry<T, OwnsObj>*& aEntry);

private:
	// Constructors and destructor
	CEntryIterator(CHashTableEntry<T, OwnsObj>** aTable, TInt aTableSize);
	void ConstructL();
	~CEntryIterator();

private:
	// Data
	CHashTableEntry<T, OwnsObj>** iTable;
	TInt iTableSize;

	RPointerArray<CHashTableEntry<T, OwnsObj> > iEntries;
	TInt iNextEntryIndex;

	// friend declarations
	friend class CHashTable<T, OwnsObj> ;
	};

//////////////////////////////////////////
// CEntryIterator<T, OwnsObj> implementation
//////////////////////////////////////////
template<class T, TBool OwnsObj> CEntryIterator<T, OwnsObj>::CEntryIterator(CHashTableEntry<T, OwnsObj>** aTable, TInt aTableSize) :
	iTable(aTable), iTableSize(aTableSize), iNextEntryIndex(0)
	{
	}

template<class T, TBool OwnsObj> CEntryIterator<T, OwnsObj>::~CEntryIterator()
	{
	iEntries.Close();
	}

template<class T, TBool OwnsObj> void CEntryIterator<T, OwnsObj>::ConstructL()
	{
	// traverse the original table and add all entries into the sequential list
	for (TInt i = 0; i < iTableSize; i++)
		{
		CHashTableEntry<T, OwnsObj>* entry = iTable[i];
		while (entry != NULL)
			{
			iEntries.AppendL(entry);
			entry = entry->Next();
			}
		}
	}

template<class T, TBool OwnsObj> TBool CEntryIterator<T, OwnsObj>::Next(CHashTableEntry<T, OwnsObj>*& aEntry)
	{
	if (iNextEntryIndex < iEntries.Count())
		{
		aEntry = iEntries[iNextEntryIndex++];

		return ETrue;
		}
	else
		{
		return EFalse;
		}
	}

template<class T, TBool OwnsObj> TBool CEntryIterator<T, OwnsObj>::Next(TPtrC8& aKey, T*& aValue)
	{
	if (iNextEntryIndex < iEntries.Count())
		{
		aKey.Set(iEntries[iNextEntryIndex]->Key());
		aValue = iEntries[iNextEntryIndex]->Obj();
		iNextEntryIndex++;

		return ETrue;
		}
	else
		{
		return EFalse;
		}
	}

//////////////////////////////////////////
// CHashTableEntry<T, OwnsObj> implementation
//////////////////////////////////////////

template<class T, TBool OwnsObj> CHashTableEntry<T, OwnsObj>* CHashTableEntry<T, OwnsObj>::NewL(const TDesC8& aKey, T* aObj)
	{
	CHashTableEntry<T, OwnsObj>* e = new (ELeave) CHashTableEntry<T, OwnsObj> (aObj);
	CleanupStack::PushL(e);
	e->ConstructL(aKey);
	CleanupStack::Pop(e);

	return e;
	}

template<class T, TBool OwnsObj> CHashTableEntry<T, OwnsObj>::CHashTableEntry(T* aObj) :
	iObj(aObj), iNext(NULL)
	{
	}

template<class T, TBool OwnsObj> CHashTableEntry<T, OwnsObj>::~CHashTableEntry()
	{
	if (OwnsObj)
		{
		delete iObj;
		}

	delete iKey;
	}

template<class T, TBool OwnsObj> void CHashTableEntry<T, OwnsObj>::ConstructL(const TDesC8& aKey)
	{
	iKey = aKey.AllocL();
	}

//////////////////////////////////////////
// CHashTable<T, OwnsObj> implementation
//////////////////////////////////////////

template<class T, TBool OwnsObj> CHashTable<T, OwnsObj>* CHashTable<T, OwnsObj>::NewLC(TInt aInitialTableSize, TReal aRehashRatio)
	{
	CHashTable<T, OwnsObj>* h = new (ELeave) CHashTable<T, OwnsObj> (aInitialTableSize, aRehashRatio);
	CleanupStack::PushL(h);
	h->ConstructL();

	return h;
	}

template<class T, TBool OwnsObj> CHashTable<T, OwnsObj>* CHashTable<T, OwnsObj>::NewL(TInt aInitialTableSize, TReal aRehashRatio)
	{
	CHashTable<T, OwnsObj>* h = NewLC(aInitialTableSize, aRehashRatio);
	CleanupStack::Pop(h);

	return h;
	}

template<class T, TBool OwnsObj> CHashTable<T, OwnsObj>::~CHashTable()
	{
	DeallocateTable();
	}

template<class T, TBool OwnsObj> CHashTable<T, OwnsObj>::CHashTable(TInt aInitialTableSize, TReal aRehashRatio) :
	iTableSize(aInitialTableSize), iRehashRatio(aRehashRatio), iNumEntries(0)
	{
	}

template<class T, TBool OwnsObj> void CHashTable<T, OwnsObj>::ConstructL()
	{
	AllocateTableL(iTable, iTableSize);
	}

template<class T, TBool OwnsObj> TInt CHashTable<T, OwnsObj>::NumEntries() const
	{
	return iNumEntries;
	}

template<class T, TBool OwnsObj> void CHashTable<T, OwnsObj>::DeallocateTable()
	{
	ResetTable();
	User::Free(iTable);
	iTable = NULL;
	}

template<class T, TBool OwnsObj> void CHashTable<T, OwnsObj>::AllocateTableL(CHashTableEntry<T, OwnsObj>**& aTable, TInt aTableSize)
	{
	TInt memSize = sizeof(CHashTableEntry<T, OwnsObj>*) * aTableSize;
	aTable = NULL;
	aTable = (CHashTableEntry<T, OwnsObj>**) User::AllocL(memSize);
	Mem::FillZ(aTable, memSize);
	}

template<class T, TBool OwnsObj> CEntryIterator<T, OwnsObj>* CHashTable<T, OwnsObj>::EntriesLC() const
	{
	CEntryIterator<T, OwnsObj>* iter = new (ELeave) CEntryIterator<T, OwnsObj> (iTable, iTableSize);
	CleanupStack::PushL(iter);
	iter->ConstructL();

	return iter;
	}

template<class T, TBool OwnsObj> void CHashTable<T, OwnsObj>::ResetTable()
	{
	for (TInt i = 0; i < iTableSize; i++)
		{
		CHashTableEntry<T, OwnsObj>* entry = iTable[i];
		while (entry != NULL)
			{
			CHashTableEntry<T, OwnsObj>* next = entry->Next();
			delete entry;
			entry = next;
			}
		}

	iNumEntries = 0;
	Mem::FillZ(iTable, sizeof(CHashTableEntry<T, OwnsObj>*) * iTableSize);
	}

template<class T, TBool OwnsObj> TReal CHashTable<T, OwnsObj>::LoadFactor()
	{
	return (TReal) iNumEntries / (TReal) iTableSize;
	}

template<class T, TBool OwnsObj> void CHashTable<T, OwnsObj>::InsertIntoTable(CHashTableEntry<T, OwnsObj>* aNewEntry, CHashTableEntry<T, OwnsObj>** aTable, TUint aIndex, TInt& aNumEntries)
	{
	// reset the next* pointer this entry might have had set
	aNewEntry->SetNext(NULL);

	CHashTableEntry<T, OwnsObj>* entry = aTable[aIndex];
	if (entry == NULL)
		{
		// no collision, insert into the table at index
		aTable[aIndex] = aNewEntry;
		}
	else
		{
		// rebuild the entire chain here, removing entries with colliding key.
		// the inserted entry will be the first in the new chain.
		aTable[aIndex] = aNewEntry;
		CHashTableEntry<T, OwnsObj>* curEntry = aNewEntry;

		while (entry != NULL)
			{
			CHashTableEntry<T, OwnsObj>* nextEntry = entry->Next();

			if (entry->Key() == aNewEntry->Key())
				{
				// collision, remove
				delete entry;
				aNumEntries--;
				}
			else
				{
				curEntry->SetNext(entry);
				curEntry = entry;
				curEntry->SetNext(NULL);
				}

			entry = nextEntry;
			}
		}

	aNumEntries++;
	}

template<class T, TBool OwnsObj> void CHashTable<T, OwnsObj>::InsertIntoTableL(const TDesC8& aKey, T* aObj, CHashTableEntry<T, OwnsObj>** aTable, TUint aIndex, TInt& aNumEntries)
	{
	CHashTableEntry<T, OwnsObj>* newEntry = CHashTableEntry<T, OwnsObj>::NewL(aKey, aObj);
	InsertIntoTable(newEntry, aTable, aIndex, aNumEntries);
	}

template<class T, TBool OwnsObj> void CHashTable<T, OwnsObj>::PutL(const TDesC8& aKey, T* aObj)
	{
	// see if we need to rehash the table
	if (LoadFactor() >= iRehashRatio)
		{
		RehashL();
		}

	TUint index = Hash(aKey, iTableSize);
	InsertIntoTableL(aKey, aObj, iTable, index, iNumEntries);
//	iNumEntries++;
	}

template<class T, TBool OwnsObj> TBool CHashTable<T, OwnsObj>::Remove(const TDesC8& aKey)
	{
	TUint index = Hash(aKey, iTableSize);
	CHashTableEntry<T, OwnsObj>* entry = iTable[index];
	CHashTableEntry<T, OwnsObj>* prevEntry = NULL;

	while (entry != NULL)
		{
		if (entry->Key() == aKey)
			{
			// match - remove this entry
			if (entry->Next() == NULL)
				{
				// this entry was last in the chain
				if (prevEntry == NULL)
					{
					// this was the only entry here. set the position in the table to NULL
					iTable[index] = NULL;
					}
				else
					{
					prevEntry->SetNext(NULL);
					}
				}
			else
				{
				// this entry had successors.
				if (prevEntry == NULL)
					{
					// this was the first entry. set the successor as the first
					iTable[index] = entry->Next();
					}
				else
					{
					// this entry was in the middle of the chain
					prevEntry->SetNext(entry->Next());
					}
				}

			delete entry;
			return ETrue;
			}
		else
			{
			// move forward in the linked list
			prevEntry = entry;
			entry = entry->Next();
			}
		}

	return EFalse;
	}

template<class T, TBool OwnsObj> T* CHashTable<T, OwnsObj>::GetL(const TDesC8& aKey) const
	{
	TUint index = Hash(aKey, iTableSize);
	CHashTableEntry<T, OwnsObj>* entry = iTable[index];

	while (entry != NULL)
		{
		if (aKey == entry->Key())
			{
			// match found, return the object
			return entry->Obj();
			}
		else
			{
			entry = entry->Next();
			}
		}

	return NULL;
	}

template<class T, TBool OwnsObj> void CHashTable<T, OwnsObj>::RehashL()
	{
	// get the entries in the current table
	CEntryIterator<T, OwnsObj>* iter = EntriesLC();

	// the new table will be the double the size of the old one
	TInt newSize = iTableSize * 2;
	TInt numEntries = 0;
	CHashTableEntry<T, OwnsObj>** newTable;
	AllocateTableL(newTable, newSize);

	// insert all the entries in the current table into the new one
	CHashTableEntry<T, OwnsObj>* entry;
	while (iter->Next(entry))
		{
		TUint index = Hash(entry->Key(), newSize);
		InsertIntoTable(entry, newTable, index, numEntries);
		}

	// deallocate old table
	User::Free(iTable);
	iTable = NULL;

	// make the new table the current one
	iTable = newTable;
	iTableSize = newSize;
	iNumEntries = numEntries;

	// cleanup
	CleanupStack::PopAndDestroy(iter);
	}

template<class T, TBool OwnsObj> TUint CHashTable<T, OwnsObj>::Hash(const TDesC8& aKey, TInt aTableSize) const
	{
	TUint sum = 0;

	for (TInt i = 0; i < aKey.Length(); i++)
		{
		sum += (TUint) aKey[i];
		}

	return (sum % aTableSize);
	}

#endif
